package com.techyuan.algorithm.dp;

import com.techyuan.algorithm.utils.PrintUtil;

/**
 * 一个序列有N个数:A[1],A[2],…,A[N],求出最长非降子序列的长度
 * longest increasing subsequence
 * LIS代码的状态方程：
 * d[i]表示：第i个数参与的lis长度
 * d[i] = max{1,d[j]+1};j<i;A[j]<A[i]
 * 最长的只需要遍历d即可
 * Created by Administrator on 2017/2/15.
 */
public class LIS {
    static int[] lis(int nums[], int n) {
        int[] lis = new int[n];
        int[] lisPrevArr = new int[n];
        int max = -1;
        for (int i = 0; i < n; i++) {
            lis[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && lis[j] + 1 > lis[i]) {
                    lis[i] = lis[j] + 1;
                    lisPrevArr[i] = j;
                }
            }
            if (max == -1 || lis[i] > lis[max]) {
                max = i;
            }
        }

        int[] lisArr = new int[lis[max]];
        int tmp = max;
        for (int i = lis[max] - 1; i >= 0; i--) {
            lisArr[i] = nums[tmp];
            tmp = lisPrevArr[tmp];
        }

        return lisArr;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{4, 6, 9, 3, 8, 1, 2, 5, 10, 5, 16, 19};
        PrintUtil.printArrPretty(lis(nums, nums.length));
    }
}
